/**
 *
 */
var MAX_GEN = 1024;
//开始
function start() {
	run();
}

function layout(cards, populations) {
	var lines = [{
		x: 0,
		y: 0,
		w: paper.w,
		prev: null,
		next: null
	}];
	var sortedByYLines = lines.sort((a, b) => {
		return a.y - b.y;
	});
	var sortedByXLines = [];

	var paperIndex = 0;
	var placedCards = [];
	while (cards.length) {
		var limitY = (paperIndex + 1) * paper.h;
		for (var i = 0; i < cards.length; i++) {
			var card = cards[i];
			for (var k = 0; k < sortedByYLines.length; k++) {
				var line = sortedByYLines[k];
				//console.log("line ", line)

				if (card.w <= line.w && (line.y + card.h) <= limitY) {
					var lineA = {
						x: line.x,
						y: line.y + card.h,
						w: card.w,
						prev: line.prev,
						next: line
					}
					line.prev = lineA;
					if (lineA.prev) {
						lineA.prev.next = lineA;
					}
					line.w = line.w - card.w;
					line.x = line.x + card.w;
					if (line.w <= 0) {
						lineA.next = line.next;
						line.deleted = true;
					}
					//和后续在同一水平
					if (lineA.next && lineA.y == lineA.next.y) {
						lineA.w = lineA.w + lineA.next.w;
						lineA.next.deleted = true;
						lineA.next = lineA.next.next;
						if (lineA.next) lineA.next.prev = lineA;
					}
					//和前面的在同一水平
					if (lineA.prev && lineA.y == lineA.prev.y) {
						lineA.w = lineA.w + lineA.prev.w;
						lineA.prev.deleted = true;
						lineA.prev = lineA.prev.prev;
						if (lineA.prev) lineA.prev.next = lineA;
					}
					lines.push(lineA)
					lines = lines.filter((it) => !it.deleted)
					sortedByYLines = lines.sort((a, b) => {
						return a.y - b.y;
					});
					sortedByXLines = lines.sort((a, b) => {
						return a.x - b.x;
					});
					//console.log(sortedByXLines);
					card.placed = true;
					placedCards.push({
						id: card.id,
						w: card.w,
						h: card.h,
						dir: card.dir
					});
					break;
				}
			}
		}

		paperIndex++;
		//console.log(cards.filter(e => e.placed))
		cards = cards.filter(it => !it.placed);

		//console.log("card length ", cards.length)
		if (cards.length && sortedByYLines.length) {

			lines = [{
				x: 0,
				y: limitY,
				w: paper.w,
				next: null
			}];

			sortedByYLines = lines.sort((a, b) => {
				return a.y - b.y;
			});
		}
	}
	sortedByXLines = lines.sort((a, b) => {
		return a.x - b.x;
	});
	//console.log(sortedByXLines);
	sortedByYLines = lines.sort((a, b) => {
		return b.y - a.y;
	});
	var topY = sortedByYLines[0].y;
	var score = totalArea * 100 / (paper.w * topY)
	var population = {
		cards: placedCards,
		paper: paperIndex,
		score: score
	}
	if (populations) populations.push(population)
	return population;
}
var totalArea = 0;
var populations = []

function showMsg(o){
	//console.log(JSON.parse(JSON.stringify(o)))
}
//创建种群
function step1() {
	populations = []
	//将卡片按从大到小顺序排列
	cards.sort((a, b) => {
		return b.w * b.h - a.w * a.h;
	});
	//编号
	var cardList = [];
	var id = 0;
	totalArea = 0;
	//w宽，h高，dir方向，style贴附风格？status是否拼版 idx索引
	cards.forEach((it, i) => {
		totalArea += it.count * it.w * it.h;
		for (var k = 0; k < it.count; k++) {
			cardList.push({
				w: it.w,
				h: it.h,
				dir: 1,
				style: 1,
				status: 0,
				id: ++id,
				idx: -1
			})
		}
	});

	var population = layout(cardList, populations);
	cardList.sort((a, b) => {
		return a.w * a.h - b.w * b.h;
	});
	cardList.forEach(e => e.placed = false)
	population = layout(cardList, populations);
	cardList.forEach(e => e.placed = false)
	cardList = shuffle(cardList)
	//console.log(cardList.length, "card length")
	population = layout(cardList, populations);
	//console.log("step1 ",showMsg(populations))

	var tmpls = jiaocha(populations)
	for (var i = 0; i < tmpls.length; i++) {
		cardList = tmpls[i];
		cardList.forEach(e => e.placed = false)
		layout(cardList, populations);
	}
	//console.log("step 1.2 ",showMsg(populations));
	return populations;
}
//选择较为优秀的个体
function select(populations) {
	populations.sort((a, b) => b.score - a.score);
	var total = 0;
	populations.forEach(x => total += Math.floor(x.score));
	//console.log("全体总分", total)

	var selected = [];
	var ti = 0;
	var MAX = Math.floor(populations.length * 4 / 100.0);
	if (MAX < 1) MAX = 2;
	while (ti < MAX) {
		var ii = Math.floor(Math.random() * total);
		var tt = 0;
		for (var i = 0; i < populations.length; i++) {
			var t = Math.floor(populations[i].score);
			if (tt + t >= ii && tt <= ii) {
				selected.push(populations[i]);
				ti++;
				break;
			}
		}
	}
	var tmpls = [];
	for (var i = 0; i < selected.length; i++) {
		for (var j = i+1; j < selected.length; j++) { 			
			var tmp = jiaocha([selected[i],selected[j]])
			tmpls.push(tmp[0])
			tmpls.push(tmp[1])
		}
	}
	return tmpls;
	// for (var i = 0; i < tmpls.length; i++) {
	// 	cardList = tmpls[i];
	// 	cardList.forEach(e => e.placed = false)
	// 	layout(cardList, populations);
	// }
}
//交叉，实现2个子代个体
function jiaocha(ps) {
	var fi = Math.floor(Math.random() * ps[0].cards.length);

	var card = ps[0].cards[fi];

	var LEN = ps[0].cards.length;
	var tmpls = [
		[],
		[]
	];
	for (var i = 0; i < LEN; i++) {
		tmpls[0].push(null)
		tmpls[1].push(null)
	}
	tmpls[0][fi] = ps[0].cards[fi];
	var id = card.id;
	var done = false;
	var k = 1;
	while (!done) {
		for (var i = 0; i < LEN; i++) {
			var c = ps[k].cards[i];
			tmpls[k][i] = c;
			if (c.id == id) {
				done = true;
				break;
			}
			k = (k + 1) % 2;;
		}
		break;
	}
	//console.log("jiaocha templates ", tmpls)
	//交换基因

	for (var i = 0; i < LEN; i++) {
		if (!tmpls[0][i]) {
			tmpls[0][i] = ps[1].cards[i];
		}
		if (!tmpls[1][i]) {
			tmpls[1][i] = ps[0].cards[i];
		}
	}
	//console.log("jiaocha templates 2 ", tmpls)
	return tmpls;
}
//计算个体适应度
function step2() {

}
//选择
function step3() {

}

//交叉
function step4() {

}

//突变
function step5() {

}

var GEN = 0;
//是否满足终止条件
function step6() {
	return GEN++>MAX_GEN;
}

function run() {
	//console.log("starting")
	var populations = step1();
	//step2();
	GEN=0;
	while (!step6()) {
		var cardLL = select(populations);
		
		for (var i = 0; i < cardLL.length; i++) {
			var cardList = cardLL[i];
			cardList.forEach(e => e.placed = false)
			layout(cardList, populations);
		}
		
		step4();
		step5();
		step2();
	}
	populations.sort((a,b)=>b.score-a.score);
	var best = populations[0]
	console.log("RESULT ",best.score,best,GEN)
}
//根据已经布置的卡片，查找剩下的空白区域。
function hello() {
	console.log("模拟遗传算法实现多尺寸矩形拼版");
}

function shuffle(arr) {
	for (let i = arr.length; i > 0; i--) {
		let temRandom = Math.floor(Math.random() * i)
		var t = arr[i - 1];
		arr[i - 1] = arr[temRandom];
		arr[temRandom] = t
	}
	return arr
}
var cards = [{
	w: 90,
	h: 54,
	count: 24
}, {
	w: 88,
	h: 58,
	count: 60
}, {
	w: 120,
	h: 60,
	count: 10
}, {
	w: 54,
	h: 54,
	count: 8
}, {
	w: 88,
	h: 48,
	count: 24
}, {
	w: 160,
	h: 100,
	count: 30
}];

var paper = {
	w: 420,
	h: 297
}

export {
	hello,
	start
}